In Section~\ref{section:domino_systems}, we found out that $\familyOf{TS} = \familyOf{DS}$ holds. Furthermore, it can be shown that $\familyOf{2OTA}$ is equal to $\familyOf{TS}$ and later we will find out that $\familyOf{PCFRE}$ is also equal to $\familyOf{TS}$ (PCFRE are projected languages of complement free regular expressions). Because we have many approaches leading to the same result, this class of languages is called the \emph{family of recognizable picture languages} abbreviated as REC. 

In this section we will reflect closure properties and the cost of emptiness and other problems. 

\begin{theorem}
	REC is closed under intersection, union, projection, vertical and horizontal concatenation, vertical and horizontal concatenation closure, projection and rotation. 
\end{theorem}

\begin{proof}
	Each closure operation can be proved by using tiling systems. This has been done in \cite{giammarresi1997twodimensional}. 
\end{proof}

These closure properties are well known from the regular string languages. But there are languages, which can be generated by using a tiling system but the complement of these languages are not tiling recognizable. That leads to the following theorem: 

\begin{theorem}
	REC is not closed under complement. 
\end{theorem}

\begin{proof}
	It can be shown, that the language L which contains only pictures of size $(2n, n)$ where the upper halves and the lower halves are identical is not in REC. But $\Sigma^{*, *} \setminus L$ is in REC. This proof can be found in \cite{giammarresi1997twodimensional}. 
\end{proof}

Regarding complexity, the results of REC are also poor in contrast to the one-dimensional representative. The membership problem for REC is NP-complete and the emptiness and universe problems are undecidable \cite{cherubini2009picture}. 

These results show that if we use the definitions of string languages and port them to two-dimensional languages, the closure properties and complexities are different.

In~\cite{prusa2012new} and~\cite{prusa2012sgraffito} the following theorem is
proved.
\begin{theorem}
REC $\subseteq \familyOf{2SA}$.	
\end{theorem}
In the proof a 2OTA is simulated by a 2SA, thus $\familyOf{OTA}$ is a subset of 
$\familyOf{2SA}$. That implies the theorem. 
\begin{theorem} 
Classes REC and $\familyOf{2DSA}$ are incomparable.
\end{theorem}
In~\cite{prusa2012new} and~\cite{prusa2012sgraffito} it was also proved that
$\bar{L}_{dup}$ is in $(REC \setminus \familyOf{2DSA})$ and $L_{perm}$ is in
$(\familyOf{2DSA} \setminus REC)$. That implies the theorem. $L_{dup}$ is 
defined in chapter~\ref{sgraffito} and $L_{perm} = \{p \hcat p \mid p \in \{0,
1\}^{*, *} \text{ and } l_1(p) = l_2(p) \text{ and each row and column of }
p \text{ contains exactly one}\\\text{ symbol } 1\}$~\cite{prusa2012sgraffito}.
Remark that $L_{perm} \subset L_{dup}$.
